package leetcode.code502;

import java.util.PriorityQueue;

public class Solution extends Solution502 {

	@Override
	public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
		int len = profits.length;
		this.mergeSort(capital, 0, len - 1, profits);
		int count = 0;// 完成项目数量
		int range = 0;// 成本最大可用边界，同时也是利润最大可用边界
		int pprofits = -1;// 最近添加入堆尾，+1是下一个入堆
		PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> o2 - o1);
		while (count < k) {
			range = findRange(capital, w, range);// 在成本中找到最大可用边界
			if (range == -1)
				return w;// 根本没有可以用的项目，这卡边界还出个“解答错误”
			for (int i = pprofits + 1; i < len && i <= range; i++) {
				pq.add(profits[i]);// 只加入没加过的利润
			}
			pprofits = range;
			if (!pq.isEmpty()) {
				w += pq.poll();// 做最大利润项目，累积到资本。
			}
			count++;// 完成一个项目，计数
		}
		return w;
	}

	private int findRange(int[] capital, int w, int range) {
		int l = range;
		int r = capital.length - 1;
		int ans = -1;// 不能为0,有可能根本没有小于w的数
		while (l <= r) {
			int m = ((r - l) >> 1) + l;
			if (capital[m] == w) {
				return m;
			} else if (capital[m] > w) {
				r = m - 1;
			} else {
				ans = m;
				l = m + 1;
			}
		}
		return ans;
	}

	public void mergeSort(int[] array, int l, int r, int[] profits) {
		if (l == r)
			return;
		int m = (r - l) / 2 + l;
		mergeSort(array, l, m, profits);
		mergeSort(array, m + 1, r, profits);
		merge(array, l, r, profits);
	}

	public void merge(int[] array, int l, int r, int[] profits) {
		int size = r - l + 1;
		int[] temp = new int[size];
		int[] temp1 = new int[size];
		int m = (r - l) / 2 + l;
		int n = m + 1;
		int p = 0;
		int lp = l;
		while (lp <= m && n <= r) {
//			temp[p++] = array[lp] < array[n] ? array[lp++] : array[n++];
			if (array[lp] < array[n]) {
				temp[p] = array[lp];
				temp1[p] = profits[lp];
				lp++;
			} else {
				temp[p] = array[n];
				temp1[p] = profits[n];
				n++;
			}
			p++;
		}
		while (lp <= m) {
			temp[p] = array[lp];
			temp1[p] = profits[lp];
			p++;
			lp++;
		}
		while (n <= r) {
			temp[p] = array[n];
			temp1[p] = profits[n];
			p++;
			n++;
		}
		for (int i = 0; i < size; i++) {
			array[l] = temp[i];
			profits[l] = temp1[i];
			l++;
		}
	}

	public static void main(String[] args) {
		Solution so = new Solution();
//		so.debug1();
//		so.debug2();
//		so.debug3();
		so.debug4();
	}

}
